package insertSort;

public class BinaryInsertSort {

	public static void main(String[] args) {
		int[] a = {3,5,8,1,6,2,0,7,4,9,-1,2};
		for (int i=1; i<a.length; i++) {
			int temp = a[i];//记录当前待插入的值，相当于哨兵
			int j = i-1;//标识已经有序的部分的最后一个index
			//折半查找先找到要插入的位置;
			int low = 0;
			int high = j;
			while (low<=high) {
				int mid = (low+high)/2;
				if (temp<a[mid]) {
					high = mid-1;
				} else {
					low = mid+1;
				}
			}
			for (int k=j;k>high;k--) {
				a[k+1] = a[k];
			}
			a[high+1] = temp;
		}
		printArray(a);
	}
	/**
	 * 打印输出数组a到控制台
	 * @param a
	 */
	private static void printArray(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+"\t");
		}
	}
	/**
	 * 交换数组中两个位置的值
	 * @param a
	 * @param i
	 * @param index
	 */
	private static void swap(int[] a, int i, int index) {
		int temp = 0;
		temp = a[i];
		a[i] = a[index];
		a[index] = temp;
	}
	

}
